package com.leetcode.offer.chapter2;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/6/16 23:08
 */
public class FindRepeatNumber_03 {

    int[] aux;

    public void sort(int[] arr, int low, int high) {
        if (low >= high) return;
        int p = partition(arr, low, high);
        sort(arr, low, p - 1);
        // 不包括切分点
        sort(arr, p + 1, high);
    }

    private int partition(int[] arr, int low, int high) {
        int l = low + 1, h = high;
        int v = arr[low];
        // 直到两者相遇
        while (true) {
            while (v > arr[l++] && l != high) ;
            while (v < arr[h--] && h != low) ;
            if (l >= h) break;
            swap(arr, l, h);
        }
        swap(arr, h, v);
        return h;
    }

    private void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public void sort2(int[] arr, int low, int high) {
        if (low >= high) return;
        int mid = (low + high) / 2;
        sort2(arr, low, mid);
        sort2(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    private void merge(int[] arr, int low, int mid, int high) {
        // 这里是mid+1
        int k = low, j = mid + 1;

        for (int i = 0; i < arr.length; i++) {
            aux[i] = arr[i];
        }

        for (int i = low; i < high; i++) {
            // 左到头和右到头
            if (k > mid) arr[i] = aux[j++];
            else if(j > high) arr[i] = aux[k++];
            // 右边比左边小
            else if(arr[k] > arr[j]) arr[i] = aux[j++];
            else arr[i] = aux[k++];
        }

    }

    // 1.Hash -- 引入一个新的空间
    // 2.排序后再查找
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(num))
                set.add(num);
            else
                return num;
        }
        return -1;
    }

    // 不修改数组来查找重复的数字

}
